package com.lw.leetcode.arr.b;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1806. 还原排列的最少操作步数
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/9 9:23
 */
public class ReinitializePermutation {

    public int reinitializePermutation(int n) {
        int[] arr = new int[n];
        Map<Integer, Integer> map = new HashMap<>();
        int t = n >> 1;
        for (int i = 0; i < n; i++) {
            if (arr[i] != 0) {
                continue;
            }
            int count = 1;
            arr[i] = 1;
            int item = (i & 1) == 0 ? i >> 1 : t + (i >> 1);
            while (item != i) {
                arr[item] = 1;
                count++;
                item = (item & 1) == 0 ? item >> 1 : t + (item >> 1);
            }
            map.put(i, count);
        }
        int a = 1;
        int b;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            b = entry.getValue();
            a = a * b / find(a, b);
        }
        return a;
    }

    private int find(int a, int b) {
        if (b == 0) {
            return a;
        }
        return find(b, a % b);
    }

}
